package g2RedBlackTree;
import java.util.*;
public abstract class MyRedBlackTree<T1>  {
	/**
	 * Compare item and t.element, using compareTo, with
	 * caveat that if t is header, then item is always larger.
	 * This routine is called if is possible that t is header.
	 * If it is not possible for t to be header, use compareTo directly.
	 */
	public static final int BLACK = 1;    
	public static final int RED   = 0;
	
	protected MyNode<T1> header;
	
	protected abstract int compare( MyNode<T1> item, MyNode<T1> t );
	public abstract Object insert(T1 key);
	protected abstract Object createNewNode(T1 key);
	public abstract void printTree( );
	/**
	 * Insert into the tree.
	 * @param item the item to insert.
	 * @throws DuplicateItemException if item is already present.
	 */
	@SuppressWarnings("unchecked")
	protected MyNode<T1> insertMe( T1 key ) {
		MyNode<T1> item = (MyNode<T1>)createNewNode(key);
		if (header == null){
			header = item;
			handleReorient( header);
			return item;
		}
		//nullNode.sequenceNumber = item.sequenceNumber;
		MyNode<T1>  current ;
		
		MyNode<T1> parent = null;
		current =  header;
		
		while( compare( item, current ) != 0 ) {
			parent = current;
			current = (compare( item, current ) < 0) 			?
					current.left : 
					current.right;			
		}

		// Insertion fails if already present
		if( current != null )
			return current;
		
		current = item;
		
		// Attach to parent
		if( compare( current, parent ) < 0 )
			parent.left = current;
		else
			parent.right = current;
		current.parent = parent;
		
		handleReorient( current);
		updateLevelParents(current);
		return current;
	}
	/**
	 * Find the smallest item  the tree.
	 * @return the smallest item or null if empty.
	 */
	public MyNode<T1>  findMin( MyNode<T1> header ) {
		if( isEmpty( ) )
			return null;

		MyNode<T1>  itr = header.right;

		while( itr.left != null )
			itr = itr.left;

		return itr;
	}

	/**
	 * Find the largest item in the tree.
	 * @return the largest item or null if empty.
	 */

	public MyNode<T1>  findMax( ) {
		if( isEmpty( ) )
			return null;

		MyNode<T1>  itr = header.right;

		while( itr.right != null )
			itr = itr.right;

		return itr;
	}
	/**
	 * Find an item in the tree.
	 * @param x the item to search for.
	 * @return the matching item or null if not found.
	 */
	public MyNode<T1>  find( T1 x ) {
		MyNode<T1> nullNodes = new MyNode<T1>(x);
		MyNode<T1> current = header;

		for( ; ; ) {
			if (current == null){
				return null;
			}
			int c = compare(nullNodes, current);
			if(  c < 0 )
				current = current.left;
			else if(c  > 0 )
				current = current.right;
			else 
				return current;
		}
	}
	/**
	 * Find an item in the tree.
	 * @param x the item to search for.
	 * @return the matching item or null if not found.
	 */
	public  ArrayList<MyNode<T1>> findPath( T1 x ) {
		ArrayList<MyNode<T1>> path = new ArrayList<MyNode<T1>>();
		
		MyNode<T1> nullNodes = new MyNode<T1>(x);
		MyNode<T1> current = header;

		for( ; ; ) {
			if (current == null){
				return null;
			}
			path.add(current);
			
			int c = compare(nullNodes, current);
			if(  c < 0 )
				current = current.left;
			else if(c  > 0 )
				current = current.right;
			else 
				return path;
		}
	}
	/**
	 * Make the tree logically empty.
	 */
	public void makeEmpty( ) {
		header = null;
	}
	/**
	 * Internal routine that is called during an insertion
	 * if a node has two red children. Performs flip and rotations.
	 * @param item the item being inserted.
	 */
	protected void handleReorient( MyNode<T1> item) {
		// Do the color flip
		if (item == null){
			return;
		}
		MyNode<T1> parent = item.getParent();
		MyNode<T1> grand = item.getGrandParent();
		MyNode<T1> uncle = item.getUncle();
		//current.color = RED;
		//current.left.color = BLACK;
		//current.right.color = BLACK;

		// case 1
		if (parent == null){
			item.color=BLACK;
			return;
		}
		// case 2
		if( parent.color == BLACK)
		{
			return;
		}
		// case 3
		if (uncle != null && uncle.color == RED) {
	        parent.color = BLACK;
	        uncle.color = BLACK;
	        grand.color = RED;
	        handleReorient(grand);
	        return;
	    }
		
		// case 4
		
		if (item == parent.right && grand!= null && parent == grand.left) {
			rotateWithLeftChild(parent);
			item = item.left;
	    }
		if (item == parent.left && grand!= null && parent == grand.right) {
			rotateWithRightChild(parent);
			item = item.right;
	    }
		handleReorient5(item);
	}
	protected void handleReorient5( MyNode<T1> item) 
	{
		
		// Do the color flip
		if (item == null){
			return;
		}
		MyNode<T1> parent = item.getParent();
		MyNode<T1> grand = item.getGrandParent();
		
	    item.parent.color = BLACK;
	    grand.color = RED;
	    if ((item == parent.left) && (parent == grand.left)) {
	    	rotateWithRightChild(grand);
	    } else if ((item == parent.right) && (parent == grand.right)) {
	    	rotateWithLeftChild(grand);
	    }
	}

	/**
	 * Internal routine that performs a single or double rotation.
	 * Because the result is attached to the parent, there are four cases.
	 * Called by handleReorient.
	 * @param item the item in handleReorient.
	 * @param parent the parent of the root of the rotated subtree.
	 * @return the root of the rotated subtree.
	 */
	/*private MyNode<T1> rotate( MyNode<T1> item, MyNode<T1> parent ) {
		if( compare( item, parent ) < 0 )
			return parent.left = compare( item, parent.left ) < 0 ?
					rotateWithLeftChild( parent.left )  :  // LL
						rotateWithRightChild( parent.left ) ;  // LR
					else
						return parent.right = compare( item, parent.right ) < 0 ?
								rotateWithLeftChild( parent.right ) :  // RL
									rotateWithRightChild( parent.right );  // RR
	}
	*/
	/**
	 * Rotate binary tree node with left child.
	 */
	
	
	private void increaseParentLevel(MyNode<T1> root){
		if (root == null){
			return;
		}
		
		
		
		increaseParentLevel(root.parent);
	}
	
	private void updateLevel(MyNode<T1> root){
		if (root==null){
			return;
		}
		
		if (root.left != null){
			root.levelLeft = Math.max(root.left.levelLeft , root.left.levelRight ) + 1;
		} else {
			root.levelLeft = 0;
		}
		if (root.right != null){
			root.levelRight = Math.max(root.right.levelLeft , root.right.levelRight ) + 1;
		} else {
			root.levelRight = 0;
		}
	}
	private void updateLevelParents(MyNode<T1> n){
		updateLevel(n);
		if (n == null){
			return;
		}
		updateLevelParents(n.parent);
	}
	private  MyNode<T1> rotateWithLeftChild( MyNode<T1> P ) {
		MyNode<T1> parent = P.parent;
		MyNode<T1> Q= P.right;
		
		P.right = Q.left;
		if (P.right != null){
			P.right.parent = P;
		}
		Q.left = P;
		P.parent = Q;
		
		updateLevel(P);
		
		if (parent == null){
			header = Q;
			header.parent = null;
		} else {
			if (parent.right == P){
				parent.right = Q;
			}else {
				parent.left = Q;
			}
			Q.parent = parent;
		}
		return Q; 
	}

	/**
	 * Rotate binary tree node with right child.
	 */
	private MyNode<T1> rotateWithRightChild( MyNode<T1> Q ) {
		MyNode<T1> parent = Q.parent;
		MyNode<T1> P= Q.left;
		
		Q.left = P.right;
		if (Q.left != null){
			Q.left.parent = Q;
		}
		P.right = Q;
		Q.parent = P;
		
		updateLevel(Q);
		
		if (parent == null){
			header = P;
			header.parent = null;
		} else {
			if (parent.left == Q){
				parent.left = P;
			}else {
				parent.right = P;
			}
			P.parent = parent;
		}
		return P;
	}

	/**
	 * Test if the tree is logically empty.
	 * @return true if empty, false otherwise.
	 */
	public boolean isEmpty( ) {
		return header.right == null;
	}
}
